
#include <stdio.h>

// 让自己永远不要失败，一点一点去变现
// 所有的一切都是为了变现
// 自己的技能去变现，自己的技术与知识去变现
// 向有需求的人去赚钱，向需求变现
// c语言实现对两个升序链表进行合并并返回。新的链表由两个原先的链表组成。
// 

struct Node
{
    int data;
    struct Node *next;
};

// 创建有头结点的链表，头节点不存储数据
struct Node * create()
{
    struct Node *L = NULL;

    if (L == NULL)
    {
        L = (struct Node *)malloc(sizeof(struct Node));
        L->next = NULL;
    }
    else
    {
        return L;
    }
    // printf("create cnt = %d \n",L->count);

    return L;
}

// 尾插法 o(n)
void invert_tail(struct Node *L, int data)
{
    struct Node *p,*q;

    p = L;

    q = (struct Node *)malloc(sizeof(struct Node));

    if (p == NULL)
    {
        printf("The list is Empty!\n");
        return;
    }

    while(p->next != NULL)
    {
        p = p->next;
    }

    p->next = q;
    p->next->next = NULL;
    p->next->data = data;
    // printf("invert cnt = %d \n",p->next->count);
}

// 头插法 o(1)
void invert_head(struct Node *L, int data)
{
    struct Node *p,*q;

    p = L;

    q = (struct Node *)malloc(sizeof(struct Node));

    if (p == NULL)
    {
        printf("The list is Empty,head node is not found!\n");
        return;
    }

    q->data = data;
    q->next = p->next;
    p->next = q;
    // printf("invert cnt = %d \n",p->next->count);
}

//升序插入o(n)
void invert_order_up(struct Node * L, int data)
{
    struct Node *p,*q;

    p = L;

    q = (struct Node *)malloc(sizeof(struct Node));

    if (p == NULL)
    {
        printf("The list is Empty,head node is not found!\n");
        return;
    }

    while((p->next != NULL) && (p->next->data < data))
    {
        p = p->next;
    }
    q->data = data;
    q->next = p->next;//p->next 是内容,因此运行到此步，说明p->next大于等于data

    p->next = q;

}

// 降序插入o(n)
void invert_order_down(struct Node * L, int data)
{
    struct Node *p,*q;

    p = L;

    q = (struct Node *)malloc(sizeof(struct Node));

    if (p == NULL)
    {
        printf("The list is Empty,head node is not found!\n");
        return;
    }

    while((p->next != NULL) && (p->next->data > data))
    {
        p = p->next;
    }
    q->data = data;
    q->next = p->next;//p->next 是内容,因此运行到此步，说明p->next大于等于data

    p->next = q;

}

//计算链表中存储的数据个数
int node_num(struct Node *L)
{
    int count = 0;
    while(L->next != NULL)
    {
        count++;
        L = L->next;
    }

    return count;
}

// 打印链表数据
void list_log(struct Node *L,char *str)
{
    printf("%s = [",str);
    struct Node *st = L->next;

    while(L->next != NULL)
    {
        printf("%d ",L->next->data);
        L = L->next;
    }
    printf("]\n");
}

// 合并两个升序链表
struct Node * mergeList(struct Node *L1, struct Node *L2)
{
    struct Node *L3 = NULL;
    L3 = create();

    struct Node *p1 = L1;
    struct Node *p2 = L2;
    struct Node *p3 = L3;

    if ((p1 == NULL) || (p2 == NULL))
    {
        printf("L1 or L2 head node is not found!\n");
        return;
    }

    // copy L1 to L3
    while(p1->next != NULL)
    {
        struct Node *q = (struct Node *)malloc(sizeof(struct Node));
        q->data = p1->next->data;
        q->next = NULL;
        p3->next = q;

        p1 = p1->next;
        p3 = p3->next;

    }

    while(p2->next != NULL)
    {
        invert_order_up(L3,p2->next->data);
        p2 = p2->next;
    }

    return L3;

}




int main(int argc, char *argv[])
{
    struct Node *L1,*L2,*L3;

    L1 = create();// 创建头节点,头节点不存储数据

    L2 = create();

    int array[6] = {2,3,12,1,4,6};
    for (int i = 0;i < 6;i++)
    {
        invert_tail(L1,i+13);
    }

    for (int i = 0;i < 6;i++)
    {
        invert_order_up(L2,array[i]);
    }

    L3 = mergeList(L1,L2);
    
    list_log(L1,"L1");
    printf("L1 count: %d \n",node_num(L1));
    list_log(L2,"L2");
    printf("L2 count: %d \n",node_num(L2));
    list_log(L3,"L3");
    printf("L3 count: %d \n",node_num(L3));

    return 0;
}